import os
import sys
class BTree:
	nodes = []
	blank = "@"
 
	def __init__(self):
		self.lnode = None
		self.rnode = None
		self.data = None
		self.level = 0
 
	@classmethod
	def createTree(self, bt, message="root"):
		node = raw_input("please input" + message)
		if(node == ""):
			bt.data = self.blank
			return
		else:
			print node
			bt.data = node
			bt.lnode = BTree()
			self.createTree(bt.lnode, "%s left" % node)
			bt.rnode = BTree()
			self.createTree(bt.rnode, "%s right" % node)
 
	@classmethod
	def preOrederTraverse(self, bt):
		if(bt):
			print bt.data,
			self.preOrederTraverse(bt.lnode)
			self.preOrederTraverse(bt.rnode)
 
	@classmethod
	def Traverse(self, bt):
		if not bt:
			return
		Q = []
		L = []
		level=bt.level = 1
		Q.append(bt)
		while not Q == []:
			tmp = Q.pop(0)
			if tmp.level==level:
				L.append(tmp.data)
			else:
				level = tmp.level
				print L
				L = []
				L.append(tmp.data)
			if  not tmp.lnode==None:
				tmp.lnode.level=tmp.level + 1
				Q.append(tmp.lnode)
 
			if  not tmp.rnode==None:
				tmp.rnode.level=tmp.level + 1
				Q.append(tmp.rnode)
		print L
 
if __name__=="__main__":
	bt = BTree()
	BTree.createTree(bt)
	BTree.preOrederTraverse(bt)
	bt.lnode.level = 1
	print '\n'
	BTree.Traverse(bt)